//
//  ViewController.swift
//  BinaryTree
//
//  Created by 郭红旗 on 2021/11/9.
//

import UIKit

struct Person:Equatable {
    var age:Int = 0
    init(_ num:Int){
        age = num
    }
}

extension ViewController{
    func testFunc() {
        
        let manager = BinaryManager<Int>.init(comparator: comparatorFuncNum(num1:num2:))
        manager.add(value: 55)
        manager.add(value: 20)
        manager.add(value: 80)
        manager.add(value: 18)
        manager.add(value: 10)
        manager.add(value: 17)
//        manager.addValue(value: 55)
//        manager.addValue(value: 20)
//        manager.addValue(value: 80)
//        manager.addValue(value: 18)
//        manager.addValue(value: 10)
        
//        manager.printFunc()
//        manager.remove(value: 20)
//        manager.printFunc()

        
        let managerOne = BinaryAVLAManager<Int>.init(comparator: comparatorFuncNum(num1:num2:))
        managerOne.add(value: 55)
        managerOne.add(value: 44)
        managerOne.add(value: 80)
        managerOne.add(value: 38)
        managerOne.add(value: 40)
        managerOne.add(value: 30)
        managerOne.add(value: 34)
        managerOne.add(value: 20)
        managerOne.add(value: 32)
//        managerOne.add(value: 31)

//        managerOne.add(value: 12)
//        managerOne.add(value: 24)
//        managerOne.add(value: 16)

//        managerOne.add(value: 4)

        managerOne.printFunc()
        managerOne.remove(value: 34)
        managerOne.printFunc()
//        managerOne.remove(value: 80)
//        managerOne.printFunc()

    }
}

class ViewController: UIViewController{
    
    /// 比较器1
    private func comparatorFunc(per:Person,per2:Person) -> Int{
        return  per.age - per2.age
    }
    /// 比较器2
    private func comparatorFuncNum(num1:Int,num2:Int) -> Int{
        return num1 - num2
    }

    override func viewDidLoad() {
        super.viewDidLoad()
        testFunc()
        /// 1、创建搜索树
//        let items = [12,5,8,14,9,7,4,10]
//        let items = [12,5,8,14,4]
//        var nodeOne: BinaryTreeModel? = createBinarySearchTree(array: items)
//        zhongxuRecursion(node: nodeOne) { num in
//            guard let result = num else {
//                return
//            }
//            print(result)
//        }
//        print("===========\(binaryTreeHeight(node: nodeOne))")
//        print("===========\(isComplete(node: nodeOne))")
//
//        postorderTraversal(node: &nodeOne)
        return

        let RBRTreeManager = BinaryRedBlackTreeManager.init(comparator: comparatorFuncNum(num1:num2:))
        RBRTreeManager.add(value: 55)
        RBRTreeManager.add(value: 38)
        RBRTreeManager.add(value: 80)
        RBRTreeManager.add(value: 88)
        RBRTreeManager.add(value: 76)
        RBRTreeManager.add(value: 46)
        RBRTreeManager.add(value: 25)
        RBRTreeManager.add(value: 17)
        RBRTreeManager.add(value: 33)
        RBRTreeManager.add(value: 50)
        RBRTreeManager.add(value: 72)
        RBRTreeManager.createNodeOne()
        print(RBRTreeManager.root!.asString)

//        RBRTreeManager.add(value: 13)
//        print(RBRTreeManager.root!.asString)
        
        RBRTreeManager.remove(element: 88)
        RBRTreeManager.remove(element: 76)
        print(RBRTreeManager.root!.asString)
        
        RBRTreeManager.remove(element: 80)
        print(RBRTreeManager.root!.asString)

//
//
        return

//        let qianArr = [12,5,4,8,14]
//        let zhongArr = [4,5,8,12,14]
//        buildTree(qianItems: qianArr, zhongItems: zhongArr)
//
//
//        let avlManager = BinaryAVLManager<Int>.init(comparator: comparatorFuncNum(num1:num2:))
//        avlManager.add(element: 13)
//        avlManager.add(element: 9)
//        print(avlManager.root!.asString)
//        avlManager.add(element: 5)
//        print(avlManager.root!.asString)
//        avlManager.add(element: 15)
//        print(avlManager.root!.asString)
//        avlManager.add(element: 14)
//        print(avlManager.root!.asString)
//        return
        
        let avlBinary = BinaryAVLTree<Int>.init(comparator: comparatorFuncNum(num1: num2:))
        avlBinary.add(element: 7)
        avlBinary.add(element: 4)
        avlBinary.add(element: 2)
        avlBinary.add(element: 5)
        avlBinary.add(element: 15)
        avlBinary.add(element: 13)
        avlBinary.add(element: 12)

        avlBinary.add(element: 11)
        print(avlBinary.getRoot()!.asString)
        avlBinary.remove(element: 15)
        print(avlBinary.getRoot()!.asString)

        return

    
        /// 2、二叉搜索树添加节点
        // 创建对象类型
        let node = BinarySearchTree<Person>.init(comparator: comparatorFunc(per: per2:))
        node.add(element: Person(10))
        node.add(element: Person(8))
        node.add(element: Person(9))
        node.add(element: Person(7))
        node.add(element: Person(11))
        print(node.getRoot()!.asString)

        return

        
        // 创建Int类型数据
        let node2 = BinarySearchTree<Int>.init(comparator: comparatorFuncNum(num1: num2:))
        node2.add(element: 8)
        node2.add(element: 2)
        node2.add(element: 11)
        node2.add(element: 5)
        node2.add(element: 1)
        node2.add(element: 3)
        node2.add(element: 7)
        print(node2.getRoot()!.asString)
        
        node2.remove(element: 2)
        print(node2.getRoot()!.asString)

        return
        
        
        /// 3、二叉搜索树前序遍历结果
        print("前序遍历开始")
        node.qianxuRecursion(node: node.getRoot()) { per in
            print(per.age)
        }
        print("前序遍历结束")
        print("前序遍历开始====")
        node2.qianxuRecursion(node: node2.getRoot()) { per in
            print(per)
        }
        print("前序遍历结束====")
        var newNode = node2.getRoot()
        node2.preorderSTraversal(node: &newNode)
        print("前序遍历结束")
        
        /// 4、二叉搜索树中序遍历结果
        print("前序遍历开始")
        node.zhongxuRecursion(node: node.getRoot()) { per in
            print(per.age)
        }
        print("前序遍历结束")


    }
    
    
    // MARK: - 创建二叉搜索树
    private func createBinarySearchTree(array:[Int]) -> BinaryTreeModel{
        var node:BinaryTreeModel?
        for value in array {
            node = createTree(node: node, value: value)
        }
        print(node?.asString ?? "")
        return node!
    }
    
    private func createTree(node:BinaryTreeModel?,value:Int) -> BinaryTreeModel{
        guard let resultNode = node else{
            let newNode = BinaryTreeModel.init(valueNum: value)
            return newNode
        }
        if value < resultNode.value {
            resultNode.leftNode = createTree(node: resultNode.leftNode, value: value)
        }else{
            resultNode.rightNode = createTree(node: resultNode.rightNode, value: value)
        }
        return resultNode
    }
    
    // MARK: - 二叉搜索树前序遍历
    /// 递归遍历
    private func qianxuRecursion(node:BinaryTreeModel?,printBlock:(Int?)->Void){
        guard let _ = node else {
            return
        }
        printBlock(node?.value)
        qianxuRecursion(node: node?.leftNode, printBlock: printBlock)
        qianxuRecursion(node: node?.rightNode, printBlock: printBlock)
    }
    /// 非递归遍历
//    public func preorderSTraversal(node:inout BinaryTreeModel?){
//        var stack = [BinaryTreeModel?]()
//        while node != nil || stack.count > 0 {
//            if node != nil {
//                print(node?.value)
//                stack.append(node)
//                node = node?.leftNode
//            }else{
//                guard let lastNode = stack.last as? BinaryTreeModel else {
//                    continue
//                }
//                node = lastNode.rightNode
//                stack.removeLast()
//            }
//        }
//    }

    // MARK: - 二叉搜索树中序遍历
    /// 递归遍历
    private func zhongxuRecursion(node:BinaryTreeModel?,printBlock:(Int?)->Void){
        guard let _ = node else {
            return
        }
        zhongxuRecursion(node: node?.leftNode, printBlock: printBlock)
        printBlock(node?.value)
        zhongxuRecursion(node: node?.rightNode, printBlock: printBlock)
    }
    /// 非递归遍历
    public func middleOrderTraversal(node:inout BinaryTreeModel?){
        var stack = [BinaryTreeModel?]()
        while node != nil || stack.count > 0 {
            if node != nil {
                stack.append(node)
                node = node?.leftNode
            }else{
                guard let lastNode = stack.last as? BinaryTreeModel else {
                    continue
                }
                print(lastNode.value)
                node = lastNode.rightNode
                stack.removeLast()
            }
        }
    }
    
    // MARK: - 二叉搜索树后序遍历
    /// 递归遍历
    private func houxuRecursion(node:BinaryTreeModel?,printBlock:(Int?)->Void){
        guard let _ = node else {
            return
        }
        houxuRecursion(node: node?.leftNode, printBlock: printBlock)
        houxuRecursion(node: node?.rightNode, printBlock: printBlock)
        printBlock(node?.value)
    }
    /// 非递归遍历
    public func postorderTraversal(node:inout BinaryTreeModel?){
        var stack = [BinaryTreeModel?]()
        var p = node
        while p != nil {
            while node?.leftNode != nil {
                stack.append(node)
                node = node?.leftNode
            }
            while node != nil && (node?.rightNode == nil || node?.rightNode == p) {
                print(node?.value ?? "")
                p = node
                if stack.count == 0 {
                    return
                }
                node = stack.last!
                stack.removeLast()
            }
            stack.append(node)
            node = node?.rightNode
        }
    }

    // MARK: - 二叉搜索树层序遍历
    public func sequenceTraversal(node:inout BinaryTreeModel?,printBlock:(Int?)->Void){
        guard let root = node else {
            return
        }
        var queueArr = [BinaryTreeModel]()
        queueArr.append(root)
        while queueArr.count > 0 {
            let childNode = queueArr.first
            printBlock(childNode?.value)
            queueArr.removeFirst()
            if let chileNode = node?.leftNode {
                queueArr.append(chileNode)
            }
            if let chileNode = node?.rightNode {
                queueArr.append(chileNode)
            }
        }
    }
    
    // MARK: - 获取二叉树的高度
    /**
     思路：从根节点逐级遍历左右子节点，子节点存在就+1。不存在直接返回。
     */
    public func binaryTreeHeight(node:BinaryTreeModel?) -> CGFloat{
        guard let root = node else {
            return 0
        }
        return 1 + max(binaryTreeHeight(node: root.leftNode), binaryTreeHeight(node: root.rightNode))
    }

    // MARK: - 判断二叉树是否为满二叉树
    
    /// 是否为叶子节点
    private func isLeaf(node:BinaryTreeModel?) -> Bool{
        return node?.leftNode == nil && node?.rightNode == nil
    }
    /**
     思路：利用层序遍历的思想
     */
    public func isComplete(node:BinaryTreeModel?) -> Bool{
        guard let root = node else {
            return false
        }
        var queueArr = [BinaryTreeModel]()
        queueArr.append(root)
        var leaf = false
        while queueArr.count > 0 {
            let childNode = queueArr.first
            queueArr.removeFirst()
            if leaf && !isLeaf(node: childNode)  {
                return false
            }
            if childNode?.leftNode != nil && childNode?.rightNode != nil {
                queueArr.append((node?.leftNode)!)
                queueArr.append((node?.rightNode)!)
            }else if (childNode?.leftNode == nil && childNode?.rightNode != nil){
                return false
            }else{
                /// 此种情况只有 （node?.leftNode == nil && node?.rightNode == nil） 或   （node?.leftNode ！= nil && node?.rightNode == nil）
                /// 在此之后遍历的节点都必须是叶子节点才能满足条件
                leaf = true
                if childNode?.leftNode != nil {
                    queueArr.append((node?.leftNode)!)
                }
            }
        }
        return true
    }
    
    public func isCompleteTwo(node:BinaryTreeModel?) -> Bool{
        guard let root = node else {
            return false
        }
        var queueArr = [BinaryTreeModel]()
        queueArr.append(root)
        var leaf = false
        while queueArr.count > 0 {
            let childNode = queueArr.first
            queueArr.removeFirst()
            
            if leaf &&  !isLeaf(node: childNode) {
                return false
            }
            
            if childNode?.leftNode != nil {
                queueArr.append((childNode?.leftNode)!)
            }else if(childNode?.rightNode != nil){
                return false
            }
            
            if childNode?.rightNode != nil {
                queueArr.append((childNode?.rightNode)!)
            }else{
                /// 此种情况只有 （node?.leftNode == nil && node?.rightNode == nil） 或   （node?.leftNode ！= nil && node?.rightNode == nil）
                leaf = true
            }
        }
        return true
    }
    
    // MARK: - 已知前序-中序  还原二叉树
    /**
     let qianArr = [12,5,4,8,14]
     let zhongArr = [4,5,8,12,14]
     */
    public func buildTree(qianItems:[Int],zhongItems:[Int]) -> BinaryTreeModel?{
 
        let length = qianItems.count
        if length == 1 {
            let root = BinaryTreeModel.init(valueNum: qianItems.first!)
            return root
        }
        let root = BinaryTreeModel.init(valueNum: qianItems.first!)
        guard let i = zhongItems.firstIndex(of: qianItems.first!) else {
            return nil
        }
        if i > 0 {
            root.leftNode = buildTree(qianItems: qianItems[1...i].map{$0}, zhongItems: zhongItems[0..<i].map{$0})
        }
        if length - i > 1 {
            root.rightNode = buildTree(qianItems: qianItems[(1+i)..<length].map{$0}, zhongItems: zhongItems[(i + 1)..<length].map{$0})
        }
        return root
    }
    
//    func reConstructForPost(preOrder: [String],inOrder: [String]) -> BinaryTreeModel? {
//
//        if inOrder.count == 0 {
//            return nil
//        }
//        var pre_left:[String] = []
//        var pre_right:[String] = []
//        var in_left:[String] = []
//        var in_right:[String] = []
//
//        let root = BinaryTreeModel()
//        root.data = preOrder[0] as NSString
//
//        var rootIndex = 0
//        //获取中序数组中的根节点位置
//        for index in 0..<inOrder.count {
//            if inOrder[index] == preOrder[0] {
//                rootIndex = index
//                break
//            }
//        }
//
//        //先序左子树 中序的左子树
//        for i in 0..<rootIndex {
//            pre_left.append(preOrder[i+1])
//            in_left.append(inOrder[i])
//        }
//
//        //先序的右子树 中序的右子树
//        for j in rootIndex+1..<inOrder.count {
//            pre_right.append(preOrder[j])
//            in_right.append(inOrder[j])
//        }
//
//        root.leftChild=reConstructForPost(preOrder: pre_left, inOrder: in_left)
//        root.rightChild=reConstructForPost(preOrder: pre_right, inOrder: in_right)
//
//        return root
//    }

}

